package com.second.app.huaweiod;

import java.util.*;

/**
 * 区间覆盖
 */
public class QujianCoverDemo {

    public static void main(String[] args) {

        int[][] test1 = {{1,3}, {2,6}, {8,10}, {15,18}};
        System.out.println("测试1: " + Arrays.deepToString(merge(test1)));


    }


    public static int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][];
        }
        // 区间起点排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        // 使用List存储结果
        List<int[]> result = new ArrayList<>();

        // 将第一个区间放入结果。
        int[] current = intervals[0];
        result.add(current);

        for (int i = 1; i < intervals.length; i++) {
            int[] next = intervals[i];

            // 判断next的起点，是不是比current的结尾小,说明有重叠
            if (current[1] >= next[0]) {
                // 合并区间
                current[1] = Math.max(current[1], next[1]);
            } else {
                current = next;
                result.add(current);
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}
